package leetcode_300;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 *@author 周杨
 *FindMedianFromDataStream_295  用一种数据结构完成 返回一个有序数组的中位数 这个有序数组支持添加数字
 *describe:用堆或者平衡二叉树 时间复杂度O(nlogN) AC 100%
 *2018年6月29日 上午10:10:58
 */
public class FindMedianFromDataStream_295 {
	PriorityQueue<Integer> leftPQ, rightPQ;//用堆
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}
	/** initialize your data structure here. */
    public FindMedianFromDataStream_295() {
        rightPQ = new PriorityQueue<>();// min heap
		leftPQ = new PriorityQueue<>(Comparator.reverseOrder());// max heap
    }
    
    public void addNum(int num) {
        if (leftPQ.size() > rightPQ.size()) {
			if (leftPQ.size() != 0 && num <= leftPQ.peek()) {
				rightPQ.add(leftPQ.poll());
				leftPQ.add(num);
			} else {
				rightPQ.add(num);
			}
		} else {
			if (rightPQ.size() != 0 && num >= rightPQ.peek()) {
				leftPQ.add(rightPQ.poll());
				rightPQ.add(num);
			} else {
				leftPQ.add(num);
			}
		}
       
    }
    
    public double findMedian() {
        if (leftPQ.size() > rightPQ.size()) {
			return leftPQ.peek();
		}
		if (rightPQ.size() > leftPQ.size()) {
			return rightPQ.peek();
		}
		return (leftPQ.peek() + rightPQ.peek()) / 2D;
    }

}
